This application is a continuation of U.S. patent application Ser. No. 12/805,567, filed Aug. 5, 2010, pending, the entire contents of which are hereby incorporated by reference in this application.
The present invention relates to a data processing apparatus configured to execute a sequence of program instructions, the data processing apparatus having checkpoint circuitry configured to store checkpoint information indicative of a state of the data processing apparatus at a selected point when executing that sequence.
In a data processing apparatus configured to execute a sequence of program instructions it is known to provide checkpoint circuitry which is configured to store checkpoint information which identifies a state of the data processing apparatus at a given point in the instruction execution sequence. This checkpoint information provides a reference point which the data processing apparatus can use to return to that point if required.
One example where such checkpoint information may be required is in a data processing apparatus configured to perform speculative instruction execution, wherein program instructions are executed before it is confirmed whether they are in fact required to be executed or not. For example, based on observation of previous outcomes, the data processing apparatus may predict the result of a branch instruction and speculatively execute the instructions which follow the expected outcome of that branch instruction. If it later turns out that the predicted outcome of the branch instruction was incorrect, checkpoint information identifying the state of the data processing apparatus when it encountered the branch instruction can be used to rewind the state of the data processing apparatus to that point, to then continue down the correct branch.
The provision of checkpoint circuitry configured to store checkpoint information in such a data processing apparatus naturally represents a cost overhead for the system, and furthermore the frequency with which such checkpoint information is stored is a trade-off which the system designer must decide. Whilst very frequent checkpointing has the advantage that a correspondingly large number of checkpoints exist to which the data processing apparatus can return and hence a large “rewind” will not be necessary, this naturally has the disadvantage that provision must be made for storing a large number of items of checkpoint information.
Another approach is to store checkpoint information on a counter basis, wherein checkpoint information is stored when a predetermined number of program instructions have been handled. However, whilst this approach allows a balance to be struck through empirical observation of how often checkpoint information is required to be referred to, it suffers from the disadvantage that checkpoints may not be stored at the most desirable point to return to in the sequence of program instructions, and hence an inefficiency arises by having to rewind the instruction execution further than is strictly necessary.
Also, it is known to store checkpoint information when particular kinds of instruction are executed, such as the branch instructions mentioned above, or instructions which are expected to be likely to result in an exception being generated. Hence, when these instructions turn out to have been incorrectly executed (wrong branch predicted) or generate an exception, checkpoint information is available allowing the data processing apparatus to return to the required instruction.
FIG. 1 schematically illustrates a known arrangement of a data processing apparatus 10, wherein checkpoint circuitry 20 and execution circuitry 30 are provided. The checkpoint circuitry 20 monitors the sequence of instructions received which are then passed on to the execution circuitry 30. The checkpoint circuitry 20 stores checkpoint information 40 in association with particular instructions in a sequence (such as branch instructions), the checkpoint information providing sufficient information for the data processing apparatus to later be able to return to the point in the sequence of instructions at which that identified instruction occurred. Hence the execution circuitry 30 can make reference to the stored checkpoint information 40, which may for example include a program counter indicative of a selected point in the sequence of instructions to then return to that point when necessary.
It is also known that checkpointing is a useful technique for data processing apparatuses that are configured to execute program instructions out of order with respect to the program sequence. Since out of order program execution allows a later instruction to be executed before an earlier instruction, if the earlier instruction causes a fault (e.g. a memory abort) it is necessary to return the data processing apparatus to a state prior to the execution of both instructions. “Checkpoint Repair for Out-of-order Execution Machines”, W. Hwu and Y. Patt, Proceedings of the 14th Annual International Symposium on Computer Architecture, pp. 18-26, 1987 provides some background information on checkpointing in out-of-order data processing apparatuses. It would be desirable to provide an improved technique for checkpointing.